package junior.贪心算法;

public class 最小生成树 {
    static int N = 6;
    static int[][] G = {{0,6,1,5,0,0},
                        {6,0,5,0,3,0},
                        {1,5,0,5,6,4},
                        {5,0,5,0,0,2},
                        {0,3,6,0,0,6},
                        {0,0,4,2,6,0}};   // 无向图,0表示无穷大,即无边
    static int[][][] GTemp = new int[N][N][2];

    public static void main(String[] args) {
        int[][][] a = new int[2][2][2];
//        //数据区
//        a[0][0][0] = 4;
//        a[0][1][0] = 5;
//        a[1][0][0] = 6;
//        a[1][1][0] = 7;
//        // 标记区
//        a[0][0][1] = 0;
//        a[0][1][1] = 1;
//        a[1][0][1] = 0;
//        a[1][1][1] = 1;
//        // 数据区
//        for (int i = 0; i < 2; i++) {
//            for (int j = 0; j < 2; j++) {
//                System.out.print(a[i][j][0]+"\t");
//            }
//            System.out.println();
//        }
//        for (int i = 0; i < 2; i++) {
//            for (int j = 0; j < 2; j++) {
//                System.out.print(a[i][j][1]+"\t");
//            }
//            System.out.println();
//        }
        Kruskal(G,GTemp);

    }

    public static void Kruskal(int[][] G,int[][][] GTemp){
        //  初始化数据
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                GTemp[i][j][1] = G[i][j];   // 上：数据区
                GTemp[i][j][0] = 0;         // 下：标记区
            }
        }
        // 打标记（对角线，即自身到自身：标记节点是否被访问：GTemp[i][i][]）
        // 依次标记出 最小边 -> 次小边 -> 最大边
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                GTemp[i][j][1] = G[i][j];
                GTemp[i][j][0] = 0;
            }
        }

    }
}
